#lang planet neil/sicp

(define (inc x)
  (+ x 1))
(define (dec x)
  (- x 1))
(define (square x)
  (* x x))
(define (max x y z)
  (define (max-iter x y)
    (if (< x y) y x))
  (if (= (max-iter x y) y) (max-iter y z) (max-iter x z))) 

(define (sqrt x)
  (define (sqrt-iter val rval)
    (define (b-enough val rval)
      (< (abs (- (* val val) rval)) 0.0001))

    (define (g-enough val rval)
      (< (/ (abs (- val (improve val rval))) (improve val rval)) 0.0001))

    (define (average x y)
      (/ (+ x y) 2))

    (define (improve x y)
      (average x (/ y x)))

    (if (g-enough val rval)
        val
        (sqrt-iter (improve val rval) rval)))
  (sqrt-iter 1.0 x))

(define (cube x)
  (define (cube-g-enough val rval)
    (< (/ (abs (- val (c-improve val rval))) (c-improve val rval)) 0.0001))

  (define (c-improve y x)
    (/ (+ (/ x (* y y)) (* 2 y)) 3))

  (define (cube-iter val rval)
    (if (cube-g-enough val rval)
        val
        (cube-iter (c-improve val rval) rval)))
  
  (cube-iter 1.0 x))


(define (Jc x)
  (if (> x 0) (* x (Jc (- x 1))) 1))

(define (dd-Jc x)
  (define (iter result count n)
    (cond ((= count (inc n)) result)
          ((= n 0) 1)
          (else (iter (* result count) (inc count) n))))
  (iter 1 1 x))
  
(define (moneyKinds kinds)
  (cond ((= kinds 1) 1)
        ((= kinds 2) 5)
        ((= kinds 3) 10)
        ((= kinds 4) 25)
        ((= kinds 5) 50)))

(define (type-count money kinds)
  (define (f m n)
    (cond ((= m 0) 1)
          ((or (< m 0) (= n 0)) 0)
          (else (+ (f m (- n 1)) (f (- m (moneyKinds n)) n)))))
  (f money kinds))


(define (dg-f n)
  (cond ((< n 3) n)
        (else (+ (dg-f (dec n)) (* 2 (dg-f (dec (dec n)))) (* 3 (dg-f (dec (dec (dec n)))))))))

(define (dd-f n)
  (define (iter x y z count n)
    (if (= count n) x
        (iter (+ x (* 2 y) (* 3 z)) x y (+ count 1) n)))
  (iter 2 1 0 2 n))

(define (cc m n)
  (if (or (= m 0) (= m n) ) 1
      (+ (cc (dec m) (dec n)) (cc m (dec n)))))

(define (is-even n)
  (= (remainder n 2) 0))

(define (fast-exp m n)
  (define (iter result m n)
    (cond ((= n 0) 1)
          ((= n 1) (* m result))
          ((is-even n) (iter result (* m m) (/ n 2)))
          (else (iter (* result m) m (dec n)))))
  (iter 1 m n))


(define (fast-mulit m n)
  (define (double x)
    (+ x x))
  (define (halve x)
    (/ x 2))
  (define (b-iter result a b)
    (cond ((= b 0) 0)
          ((= b 1) (+ a result))
          (else (b-iter (+ result a) a (- b 1)))))
  (define (g-iter result a b)
    (cond ((= b 0) 0)
          ((= b 1) (+ a result))
          ((is-even b) (b-iter result (double a) (halve b)))
          (else (g-iter (+ a result) a (- b 1)))))
  (b-iter 0 m n))


(define (prime n) 
  (define (div a b)
    (= (remainder a b) 0))

  (define (find-div n cheak )
    (cond ((> (square cheak) n ) n)
          ((div n cheak) cheak)
          (else (find-div n (+ cheak 2) ))))

  (define (smallest-div n)
    (find-div n 2))
          
  (= (smallest-div n) n))

(define (expmod m n p)
  (cond ((= n 0) 1)
        ((is-even n) (remainder (square (expmod m (/ n 2) p)) p))
        (else (remainder (* m (expmod m (- n 1) p)) p))))

(define (fermat-test n)
  (define (try a)
    (= (expmod a n n) a))
  (try (+ (random (- n 1)) 1)))

(define (fermat-timer n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fermat-timer n (- times 1)))
        (else false)))

(define (m-sympson f a b n)
  (define h (/ (- b a) n))
  (define (func k)
    (f (+ a (* k h))))
  (define (iter result k)
    (if (> k n) result
        (iter (+ result (func k)) (inc k))))
  (* (/ h 3) (iter 0 0)))

(define (c-sympson f a b n)
  (define h (/ (- b a) n))
  (define (func k)
    (f (+ a (* k h))))
  (define (next x)
    (inc x))
  (define (sum term a next b)
    (define (iter result k)
      (if (> k n)
          result
          (iter (+ result (func k)) (next k))))
    (* (/ h 3) (iter 0 0)))
  (sum func 0 next n))

(define (pi-mulit n)
  (define (iter a b result)
    (cond ((and (is-even n) (= a (+ n 2))) (* result (/ a b)))
          ((and (not (is-even n)) (= b (+ n 2))) (* result (/ a b)))
          ((> a b) (iter a (inc a) (* result (/ a b))))
          (else (iter (inc b) b (* result (/ a b))))))
  (iter 2.0 3.0 1))


(define (dg-pi-mulit n)
  (define (iter n r)
    (cond ((= n 0) r)
          ((is-even n) (* r (iter (dec n) (/ (+ n 2) (inc n)))))
          ((not (is-even n)) (* r (iter (dec n) (/ (inc n) (+ n 2)))))))        
  (iter n 1.0))

(define (mulit-f term a next b)
  (if (> a b)
      1
      (* (term a) (mulit-f term (next a) next b))))

(define (dg-mulit-pi n)
  (define (next x)
    (+ x 1))
  (define (iter n)
    (cond ((is-even n) (/ (+ n 2.0) (inc n)))
          ((not (is-even n)) (/ (inc n) (+ n 2.0)))))
  (mulit-f iter 1 next n))
  
(define (accumulate combiner value term a next b)
  (if (> a b)
      value
      (combiner (term a) (accumulate combiner value term (next a) next b))))
(define (test-accul n)
  (define (next x)
    (+ x 1))
  (define (iter n)
    (cond ((is-even n) (/ (+ n 2.0) (inc n)))
          ((not (is-even n)) (/ (inc n) (+ n 2.0)))))
  (accumulate * 1 iter 1 next n))

(define (filter-accul filter combiner value term a next b)
  (if (> a b)
      value
      (combiner (filter (term a)) (filter-accul filter combiner value term (next a) next b))))

(define (ss-sum a b)
  (define (next x)
    (inc x))
  (define (filter x)
    (if (prime x) x 0))
  (define (iter x) x)
  (filter-accul filter + 0 iter a next b))

(define (gcd n m)
  (if (= m 0)
      n
      (gcd m (remainder n m))))

(define (mulit-hs  n)
  (define (next x)
    (inc x))
  (define (filter x)
    (if (= (gcd x n) 1)
        x
        1))
  (define (iter x) x)
  (filter-accul filter * 1 iter 1 next n))
        
(define (fixed-point f guess)
  (define (is-enough v1 v2)
    (< (/ (abs (- v1 v2)) v2) 0.0001))
  (define (iter guess)
    (let ((next (f guess)))
      (newline)
      (display next)
      (if (is-enough guess next)
          next
          (iter next))))
  (iter guess))

(define (gold-line x)
  (+ 1 (/ 1 x)))
(define (test-sin x)
  (sin x))
(define (test-log x)
  (/ (+ x (/ (log 1000) (log x))) 2))

(define (cont-frac n d k)
  (define (iter r k)
    (let ((term (lambda (x) (/ n (+ d x)))))
      (if (= k 0)
          r
          (iter (term r) (dec k)))))
  (iter 2.0 k))

(define (dd-cont-frac n d k)
  (define (iter c)
    (let ((term (lambda (x) (/ n (+ d x)))))
      (if (= c k)
          2.0
          (term (iter (inc c))))))
  (iter 1))

(define (cubic a b c)
  (lambda (x) (+ (* x (square x)) (* a (square x)) (* b x) c)))
(define (f-double f)
  (lambda (x) (f (f x))))

(define (compose f g)
  (lambda (x) (f (g x))))

(define (repeated f n)
  (define (iter n x)
    (if (= n 1)
        (f x)
        (f (iter (dec n) x))))
  (lambda (x) (iter n x)))

(define (smooth f)
  (lambda (x) (/ (+ (f (- x 0.0001)) (f x) (f (+ x 0.0001))) 3)))

((repeated (smooth (lambda (x) (square x))) 5) 5) 
    